package pers.sloera.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 找出给定方程的正整数解
 *
 * @author sloera
 * @date 2023-02-18 19:48:38
 */
class FindPositiveIntegerSolutionForAGivenEquation {
    public static void main(String[] args) {
        Solution solution = new FindPositiveIntegerSolutionForAGivenEquation().new Solution();
        List<List<Integer>> solution1 = solution.findSolution((x, y) -> x + y, 5);
        System.out.println(solution1);
    }

    // This is the custom function interface.
    // You should not implement it, or speculate about its implementation

    /**
     * 单调递增 说明x和y，都是递增的
     */
    @FunctionalInterface
    interface CustomFunction {
        // Returns f(x, y) for any given positive integers x and y.
        // Note that f(x, y) is increasing with respect to both x and y.
        // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
        public int f(int x, int y);

    }

    ;

    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public static final int MIN = 1;
        public static final int MAX = 1000;

        public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
            ArrayList<List<Integer>> result = new ArrayList<>();
            for (int x = MIN; x <= MAX; ) {
                // 单词递增 不存在同一个x对应两个y值都为z
                int y = findNextY(x, z, customfunction);
                if (y >= 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(x);
                    list.add(y);
                    result.add(list);
                }
                x = findNextX(x + 1, z, customfunction);
                if (x < 0) {
                    break;
                }
            }
            return result;
        }

        // 判断每个x，在y的最小/大值内，是否有机会等于z
        private int findNextX(int x, int z, CustomFunction customfunction) {
            while (x <= MAX) {
                if (customfunction.f(x, MIN) > z || customfunction.f(x, MAX) < z) {
                    x++;
                    continue;
                }
                return x;
            }
            return -1;
        }

        // 在y的有效区间 y, MAX内判断是否有相等的值
        private int findNextY(int x, int z, CustomFunction customfunction) {
            if (customfunction.f(x, MAX) < z) {
                return -1;
            }
            int y = MIN;
            while (y <= 1000) {
                // y, z, MAX
                if (z == customfunction.f(x, y)) {
                    return y;
                } else if (customfunction.f(x, y) > z) { // 递增，如果大于，后面没有查找的必要了
                    return -1;
                } else {
                    y++;
                }
            }
            return -1;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
